import x10.util.Random; 
import x10.util.Timer; 

public class Main
{
    static val HEIGHT_AXIS = 0;
    static val WIDTH_AXIS  = 1;

    static val CANDIDATES = 1;        // Increase this value and add other items to the opt_funcs array to try different approaches.

    static val USE_MEDIAN = false;    // Will be set to true for grading to ensure more stable timing results

    static val INPUT_LEN = 1024*1024*8;

    public static def main(Array[String])
    {
        var ref_histo_func: BaseHisto = new RefHisto();

        val opt_funcs: Array[BaseHisto] = new Array[BaseHisto](CANDIDATES+1);
            opt_funcs(0) = new OptHisto();

        val times:   Array[double] = new Array[double](0..CANDIDATES*0..2);

        val results: Array[String] = new Array[String](opt_funcs.region);

        for (i in opt_funcs)                                                  // Benchmark each optimized function ...
            if (opt_funcs(i) != null)
                times(i.coords()(0), 0) = run_speed_test(opt_funcs(i));

        if (USE_MEDIAN)
        {
            for (i in opt_funcs)                                                  // Benchmark each optimized function ...
                if (opt_funcs(i) != null)
                    times(i.coords()(0), 1) = run_speed_test(opt_funcs(i));

            for (i in opt_funcs)                                                  // Benchmark each optimized function ...
                if (opt_funcs(i) != null)
                    times(i.coords()(0), 2) = run_speed_test(opt_funcs(i));
        }
        else
        {
            // If we aren't timing using a median of 3 runs, just set all 3 run times to the same value
            for (i in opt_funcs) 
                if (opt_funcs(i) != null)
                {
                    times(i.coords()(0), 1) = times(i.coords()(0), 0);
                    times(i.coords()(0), 2) = times(i.coords()(0), 0);
                }
        }

        for (i in opt_funcs)                                                  // And print out the results :-)
        {
            if (opt_funcs(i) != null)
            {
                val med = median (times(i.coords()(0), 0),
                                  times(i.coords()(0), 1),
                                  times(i.coords()(0), 2));

                val median_speedup_String: String = String.format("%.2f", new Array[Any](1, med));
                val speedup_String_0     : String = String.format("%.2f", new Array[Any](1, times(i.coords()(0), 0)));
                val speedup_String_1     : String = String.format("%.2f", new Array[Any](1, times(i.coords()(0), 1)));
                val speedup_String_2     : String = String.format("%.2f", new Array[Any](1, times(i.coords()(0), 2)));

                val result = "    " + opt_funcs(i).getName() + "  GEOMETRIC MEAN SPEEDUP: "
                                    + median_speedup_String
                                    + "   [" + speedup_String_0 + "x"
                                    + "    " + speedup_String_1 + "x"
                                    + "    " + speedup_String_2 + "x]";

                Console.OUT.println(result);
            }
        }
    }

    static def median(v1: double, v2: double, v3: double)
    {
        if (v1 > v2)
        {
            if (v3 > v1)            // v3 > v1 > v2
                return v1;
            else if (v3 > v2)       // v1 > v2 > v1
                return v3;
            else                    // v1 > v2 > v1
                return v2;
        }
        else                        // v1 <= v2
        {
            if (v3 > v2)            // v3 > v2 > v1
                return v2;
            else if (v3 > v1)       // v2 > v3 > v1
                return v3;
            else                    // v2 > v1 > v3
                return v1;
        }
    }

    static def run_speed_test(opt_histo_func: BaseHisto) : double
    {
        var ref_histo_func: BaseHisto = new RefHisto();
        val speedup                   = compute_score(ref_histo_func, opt_histo_func);
        return speedup;
    }

    static def compute_score(ref_func: BaseHisto, hist_func: BaseHisto)
    {
        val widths  = new Array[int](7..12, (p:Point(1)) => ((1 << p(0)) - 1)); 

        var score   : double = 1.0;
        var test_cnt: double = 0;

        for (width in widths)
        {
            val y_max = widths(width);
            val x_max = widths(width);

            val rand     = new Random();
            val ref_hist = make_histogram(x_max + 1, y_max+1, 0xFF);
            val input    = new Array[int](INPUT_LEN,  (p:Int) => rand.nextInt((x_max + 1)*(y_max + 1)));
      
            // Establish Baseline 
            val ref_time_in_millis = run_histo_func(ref_func, ref_hist, input);
            val sum = sum_histogram(ref_hist);
            Console.OUT.println("\tRef bin sum: " + ((sum == INPUT_LEN) ? "correct" : "INCORRECT!!!!!!!!!!!!!!!!!!!!!"));

            val opt_time_in_millis = compare_performance(hist_func, ref_hist, input);

            val speedup = ref_time_in_millis/opt_time_in_millis;

            score    *= (ref_time_in_millis/opt_time_in_millis);
            test_cnt += 1;

            val params: Array[Any] = new Array[Any](1, speedup);

            val speedup_String: String = String.format("%.2f", params);

            Console.OUT.println("Speedup: " + speedup_String + "x  [" + opt_time_in_millis + " vs. " + ref_time_in_millis + "]\n");
        }

        // Geometric mean is the nth root.
        return Math.pow(score, 1.0/test_cnt);
    }

    static def make_histogram(width: int, height: int, fill: int) : Array[int]{rank==2}
    {
        val hist = new Array[int]((0..(height-1))*(0..(width-1)), (p:Point(2)) => fill);
        return hist;
    }

    // Run a histogram function.  'input' contains bin indexes.  'hist' is the histogram to fill.
    // Return the number of milliseconds it took to fill the histogram.
    //
    static def run_histo_func(hist_func: BaseHisto, hist: Array[int]{rank==2}, input: Array[int]{rank==1}) : double
    {
        val start = Timer.milliTime();
        hist_func.histogram    (hist, input);
        val end = Timer.milliTime();
        val time_in_millis = end - start;
        Console.OUT.println(hist_func.getName() + ": Time (" +
                            (hist.region.max(HEIGHT_AXIS) + 1) + " x " + (hist.region.max(WIDTH_AXIS) + 1) +
                            "): " + time_in_millis + " ms.");
        return time_in_millis;
    }

    // Fill a histogram with the values from 'input'.
    // Compare the results with the passed in filled histogram 'ref_hist'
    // Return the time taken to fill the histogram.
    //
    static def compare_performance(hist_func: BaseHisto, ref_hist: Array[int]{rank==2}, input: Array[int]{rank==1}) : double
    {
        val hist = new Array[int]((0..ref_hist.region.max(HEIGHT_AXIS))*(0..ref_hist.region.max(WIDTH_AXIS)), (p:Point(2)) => 0xCC);

        val time_in_millis = run_histo_func(hist_func, hist, input);

        val diffs = compare_histogram(ref_hist, hist);
        Console.OUT.println("\tHistograms : " + ((diffs == 0)         ? "match"   : "DIFFER!!!!!!!!!!!!!!!!!!!!!"));

        return time_in_millis;
    }

    // Add up the contents of all the bins in a histogram.
    // This can be a useful sanity check that no input values
    // have been lost.
    //
    static def sum_histogram(hist: Array[int]{rank==2})
    {
        var sum: int = 0;

        for (bin in hist)
            sum += hist(bin);

        return sum;
    }

    // Compare two histograms, bin-by-bin.  Return the number of bins that differ.
    // This function assumes that the two histograms are the same size/shape.
    //
    static def compare_histogram(hist_a: Array[int]{rank==2}, hist_b: Array[int]{rank==2})
    {
        var diffs: int = 0;

        for (bin in hist_a)
            diffs += (hist_a(bin) == hist_b(bin)) ? 0 : 1;

        return diffs;
    }


    // Dump some contents of the histogram to stdout
    //
    // The histograms can be huge, so this prints the corners of the
    // histogram.  PRINT_BAND determines how large each corner will be.
    //
    static def print_histogram(hist: Array[int]{rank==2})
    {
        val PRINT_BAND  = 3;

        val left_print_region   = 0..PRINT_BAND;
        val right_print_region  = (hist.region.max(WIDTH_AXIS) - PRINT_BAND)..(hist.region.max(WIDTH_AXIS));
        val top_print_region    = 0..PRINT_BAND;
        val bottom_print_region = (hist.region.max(HEIGHT_AXIS) - PRINT_BAND)..(hist.region.max(HEIGHT_AXIS));

        for ([y] in top_print_region)
        {
            Console.OUT.print("\t");
            for ([x] in left_print_region)
                Console.OUT.print("" + hist(y,x) + "\t");
            Console.OUT.print(" ... \t");
            for ([x] in right_print_region)
                Console.OUT.print("" + hist(y,x) + "\t");
            Console.OUT.println();
        }

        for ([y] in 0..3)
        {
            Console.OUT.print("\t");
            for ([x] in left_print_region)
                Console.OUT.print(":\t");
            Console.OUT.print(" ... \t");
            for ([x] in right_print_region)
                Console.OUT.print(":\t");
            Console.OUT.println();
        }

        for ([y] in bottom_print_region)
        {
            Console.OUT.print("\t");
            for ([x] in left_print_region)
                Console.OUT.print("" + hist(y,x) + "\t");
            Console.OUT.print(" ... \t");
            for ([x] in right_print_region)
                Console.OUT.print("" + hist(y,x) + "\t");
            Console.OUT.println();
        }
    
        val sum = sum_histogram(hist);
        Console.OUT.println("\t\t\tHistogram Sum: " + sum);
    }
}
